package com.hspedu.newData.dmsxl.dfs;
/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-28 
 * @Version: 1.0
 */

// todo
public class LC79单词搜索 {

    private int[][] dir = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
    public boolean exist(char[][] board, String word) {

        int m = board.length;
        int n = board[0].length;

        boolean[][] visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                boolean flag = dfs(board,i,j,visited,word,0);
                if (flag){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board,int x,int y,boolean[][] visited,String s,int key){
        if (board[x][y] != s.charAt(key)){
            return false;
        }
        if (key==s.length()-1){
            return true;
        }
        boolean result = false;
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {

            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];

            if (nextX<board.length&&nextY<board[0].length&&nextX>=0&&nextY>=0){
                if (!visited[nextX][nextY]){
                    boolean flag = dfs(board,nextX,nextY,visited,s,key+1);
                    if (flag){
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[x][y] = false;
        return result;
    }
}
